# 비터비 알고리즘 (Viterbi Algorithm)

**비터비 알고리즘**(Viterbi Algorithm)은 가장 가능성이 높은 상태 시퀀스(최우경로)를 찾기 위한 동적 계획법(Dynamic Programming) 기반의 알고리즘입니다. 주로 은닉 마르코프 모델(Hidden Markov Model, HMM)과 같은 확률적 모델에서 관찰된 시퀀스 데이터가 주어졌을 때, 그 데이터를 생성했을 가장 확률이 높은 숨겨진 상태의 시퀀스를 추정하는 데 사용됩니다. 1967년 제임스 비터비(James Viterbi)가 통신 분야에서 오류 정정 부호를 복호화하기 위해 처음 제안했으며, 이후 자연어 처리, 음성 인식, 생정보학 등 다양한 분야에서 핵심적인 역할을 하고 있습니다.

## 개요 및 배경

비터비 알고리즘의 핵심 목적은 "최적의 경로 찾기"입니다. 많은 경우, 시스템의 내부 상태(은닉 상태)는 직접 관측할 수 없지만, 외부에서 관찰 가능한 데이터(관측 시퀀스)를 통해 내부 상태를 추론해야 하는 상황이 발생합니다. 예를 들어, 비가 올지 맑을지(은닉 상태)를 알 수 없지만, 길의 젖음 정도(관측 데이터)를 통해 날씨를 추론하는 경우입니다.

이 알고리즘은 브루트 포스(완전 탐색) 방식과 달리, 중복 계산을 피하고 부분 문제의 최적해를 조합하여 전체 최적해를 찾는 동적 계획법의 원리를 적용합니다. 이로 인해 지수 함수적 시간 복잡도를 다항식 시간 복잡도로 줄여 효율적으로 해를 구할 수 있습니다.

## 알고리즘의 작동 원리

비터비 알고리즘은 단계별로 진행되며, 각 단계에서 가장 확률이 높은 경로의 확률값과 해당 경로의 이전 상태를 저장합니다. 주요 단계는 다음과 같습니다.

### 1. 초기화 (Initialization)
시간 $t=1$에서 각 상태 $i$에 대해 초기 확률과 관측 확률을 곱한 값을 계산합니다.
$$ \delta_1(i) = \pi_i b_i(o_1) $$
여기서 $\pi_i$는 상태 $i$의 초기 확률, $b_i(o_1)$은 상태 $i$에서 관측값 $o_1$이 발생할 확률입니다.

### 2. 재귀적 단계 (Recursion)
시간 $t=2$부터 $T$까지 각 상태 $j$에 대해 이전 시간 $t-1$의 모든 상태 $i$에서 전이 확률과 현재 상태의 관측 확률을 곱한 값 중 최대값을 선택합니다.
$$ \delta_t(j) = \max_{1 \le i \le N} [\delta_{t-1}(i) a_{ij}] b_j(o_t) $$
여기서 $a_{ij}$는 상태 $i$에서 상태 $j$로 전이할 확률입니다. 또한, 최대값을 만든 이전 상태 $i$를 $\psi_t(j)$로 저장하여 나중에 경로를 추적할 수 있도록 합니다.

### 3. 종료 (Termination)
마지막 시간 $T$에서 가장 큰 확률을 가진 상태를 찾습니다.
$$ P^* = \max_{1 \le i \le N} [\delta_T(i)] $$
$$ q_T^* = \arg\max_{1 \le i \le N} [\delta_T(i)] $$

### 4. 경로 추적 (Path Backtracking)
저장된 $\psi$ 값을 역순으로 추적하여 가장 확률이 높은 상태 시퀀스 $q_1^*, q_2^*, ..., q_T^*$를 복원합니다.

## 주요 응용 분야

비터비 알고리즘은 다양한 분야에서 광범위하게 적용됩니다.

*   **자연어 처리 (NLP)**: 품사 태깅(Part-of-Speech Tagging)이나 개체명 인식(Named Entity Recognition)에서 문장의 각 단어가 어떤 품사나 개체 유형에 해당하는지 확률적으로 결정할 때 사용됩니다.
*   **음성 인식**: 음성 신호의 프레임별로 어떤 음소(phoneme)가 발음되었는지를 추정하는 데 사용됩니다.
*   **생정보학**: DNA 또는 단백질 서열 분석에서 유전자 영역(Gene Finding)이나 단백질의 2차 구조 예측에 활용됩니다.
*   **통신 공학**: 원래의 데이터 비트열을 복원하기 위해 채널 오류를 보정하는 데 사용됩니다.

## 알고리즘의 장단점

### 장점
*   **효율성**: 동적 계획법을 사용하여 $O(N^2 T)$의 시간 복잡도를 가지며, 여기서 $N$은 상태의 수, $T$는 시퀀스의 길이입니다. 이는 완전 탐색의 $O(N^T)$에 비해 압도적으로 빠릅니다.
*   **정확성**: 주어진 모델 하에서 가장 확률이 높은 단일 경로를 보장합니다.

### 단점
*   **국소 최적해**: 비터비 알고리즘은 전역 최적해(global optimum)를 찾는 것이 아니라, 주어진 모델에 기반한 가장 확률이 높은 경로를 찾습니다. 모델의 파라미터(전이 확률, 관측 확률)가 부정확하면 결과도 부정확할 수 있습니다.
*   **단일 경로 제한**: 여러 개의 가능한 경도를 동시에 고려하지 않으므로, 확률이 매우 근접한 여러 경로가 존재할 경우 다른 대안을 제시하지 못합니다.

## 관련 알고리즘 및 비교

비터비 알고리즘과 유사하게 상태 시퀀스를 추정하는 방법으로는 **전진-후진 알고리즘**(Forward-Backward Algorithm)이 있습니다. 전진-후진 알고리즘은 특정 시점의 상태가 특정 값일 **사후 확률**(posterior probability)을 계산하는 데 사용되며, 비터비 알고리즘이 **최우 경로**(most likely sequence)를 찾는 것과 구별됩니다. 또한, **키르비 필터**(Kalman Filter)는 연속적인 상태 공간에서 유사한 추론 문제를 해결하는 데 사용됩니다.

## 참고 자료

*   Viterbi, A. (1967). "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm". *IEEE Transactions on Information Theory*.
*   Rabiner, L. R. (1989). "A tutorial on hidden Markov models and selected applications in speech recognition". *Proceedings of the IEEE*.
*   Bishop, C. M. (2006). *Pattern Recognition and Machine Learning*. Springer.